Assume we are given a road map, like the one below, that shows the distance
between those pairs of cities that are directly connected by a single
stretch of highway.  How can we produce a table that shows the length of
the shortest route between each pair of cities?











A standard paradigm for approaching problems taht involve a large number of
entities (in this case, cities) is to solve the problem first for small
subsets, then larger and larger ones.  If we had already solved the problem
for six cities, and solved the results in an array, what would we need to
do when a seventh city is introduced?

(1) The distance from the new city to itself is always zero.

(2) The best route from the new city (`A') to one of the earlier cities
(`B') is either a direct road, or consists of going from A to another of
the earlier cities (`C') and taking the best route from C to B, naturally
not passing through A; by trying every possible city in the role of C, we
can find the shortest route from A to B.

(3) The best route from city D to city E is either the previous best route,
or goes from D to the new city A, and from A to E.  In the latter case,
step 3 has already found the best such routes, and we can add their
lengths.

By using the calculations implied by (1), (2), and (3) for each city in
turn, we build up the table until it reflects the entire map.  To present
the algorithm in Pascal, assume we have an array DIRECT, where D[I,J] is a
very large number BIG, like 10000, which is sure to be larger than the
length of the shortest route.

We want to fill in an array DISTANCE, so that DISTANCE[I,J] is the length
of the shortest route from city  I to city J.  The rules above are the
basis of a Pascal algorithm.

	FOR A:=1 TO N DO
		DISTANCE [A,A]:=0;
		FOR B:=1 TO A-1 DO
			DIST :=DIRECT[A,B];
			FOR C:=1 TO A-1 DO
				IF DIST > DIRECT[A,C]+DISTANCE[C,B]
					THEN DIST:=DIRECT[A,C]+DISTANCE[C,B];
		DISTANCE[A,B]:=DIST;DISTANCE[B,A]:=DIST;
		FOR D:=1 TO A-1 DO
			FOR E:=1 TO A-1 DO
				IF DISTANCE[D,A]+DISTANCE[A,E] < DISTANCE[D,E]
				THEN DISTANCE[D,E]:=DISTANCE[D,A]+DISTANCE[A,E]

Exercise:  Modify the above algorithm so that it also computes FIRST[I,J],
the number of the first city on the shortest route from I to J.

Exercise:  After performing the above modification, add a stage to the
algorithm that will read the numbers of two cities and print out the
numbers of all the cities along the shortest route between them.

Here is a simpler Pascal algorithm for the same problem; it is, however,
harder to explain.  See if you can discover why it works.

	FOR I:=1 TO N DO
		FOR K:=1 TO N DO
			DISTANCE[I,K]:=DIRECT[I,K];
	FOR I:=1 TO N DO
		FOR K:=1 TO N DO
			FOR J:=1 TO N DO
				IF DISTANCE[I,K]>DISTANCE[I,J]+DISTANCE[J,K]
					THEN DISTANCE[I,K]:=DISTANCE[I,J]+DISTANCE[J,K]